An ad hoc computing network comprises computing nodes that form a network topology amongst themselves on an ad hoc basis. Unlike traditional networks whose network topologies are planned, provisioned, or configured, ad hoc networks typically must rely on self-configuring abilities of their respective nodes to discover neighbors and form network topologies. Furthermore, because a node in an ad hoc network is allowed to autonomously alter its link relationships with other nodes, a network topology previously formed can undergo changes from time to time in a seemingly random manner.
For example, a node in an ad hoc computing network may decide to withdraw from the network. The withdrawal would cause all the link relationships (to, from or through the node) to be rendered invalid. Therefore, the remaining nodes in the ad hoc computing network need to reconfigure themselves drawing on their self-configuring capabilities. Specifically, this reconfiguration can take the form of discovering one or more new routes without the withdrawn node playing any role therein.
In an ad hoc network such as a wireless mobile network that implements AODV, to forward a data packet to a destination node, a forwarding node (a special example of which is an originating node of a data packet) can initiate a route discovery if a path to the destination node does not exist or is no longer valid. A route may be considered as invalid if it has been idle for a considerable amount of time, for example. To discover a (new) valid path and/or a next hop node, the forwarding node can broadcast a route request message. This broadcast can be made by flooding the route request message in an immediate area of the forwarding node. The scope or size of the immediate area of the forwarding node flooded depends on a transmission power level accompanying the forwarding node's radio signal(s) which encodes the route request message.
If a receiving node of the route request message has a valid path to the destination node, the receiving node can reply to the forwarding node in a route reply message. In response to receiving the reply, the forwarding node may create or update a route to the destination node in its routing table using the receiving node as a next hop, or may add a proposed routing path described in the receiving node's reply to a set of candidate routing paths from which an optimal routing path may be chosen.
If the receiving node of the route request message has no valid path to the destination node, the receiving node can further broadcast a request for a route to the destination by flooding a new route request message in its own immediate area. The scope or size of the receiving node's immediate area flooded depends on a transmission power level accompanying the receiving node's radio signal which encodes the new route request message. This process continues until a valid routing path has been established between the originating node and the destination node.
Thus, ripple-like effects are typically caused each time when a route discovery must be made; many nodes in the ad hoc network may be involved in successive flooding of request messages and generating of response messages.
Since nodes in an ad hoc network typically are mobile devices that carry batteries as their energy sources, these existing techniques have a serious disadvantage of draining precious battery powers of nodes, if the nodes are involved in frequent route discoveries, as would be expected in a relatively mobile ad hoc network.
Under the existing techniques, if there is more than one path to a destination node, a route that contains the fewest hops is selected as a best path to the destination. This best path would be used to route any unicast messages to the destination node. However, if a best path with the fewest hops has longer hop-to-hop distances than another path with more hops but shorter hops, the power required to transmit a signal through the best path might be much higher than the power required to do the same on the other route, as it is well known that the power required is inversely proportional to the distance squared between a transmitting node and a receiving node (e.g., a 2× increase of distance causes 4× increase of power consumption). Thus the best path may consume much more power. If the given forwarding node had only a limited battery capacity or otherwise were sensitive to power consumption, then the best path with the fewest hops would not be optimal.
Thus, an improved way of selecting a route in an ad hoc network is needed.